Euler Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.


In [2]:
from itertools import combinations_with_replacement as combos

fact = [1]
prod = 1
for k in range(1, 10):
    prod *= k
    fact.append(prod)

total = 0
for d in range(2, 9):
    for v in combos(range(10), d):
        N = sum(fact[x] for x in v)
        if tuple(sorted(map(int, str(N)))) == v:
            total += N
print(total)


40730

Explanation: If $N$ is a $d$-digit number, then $10^{d-1} \le N < 10^d$, and the sum of factorials of the digits of $N$ is at most $9! \cdot d$. Consequently, if $N$ equals the sum of factorials of its digits, then $10^{d-1} \le 9! \cdot d$, which implies $d \le 8$.

Instead of checking all numbers less than $10^8$, we check all combinations of at most 8 digits, with repetition allowed. For each combination $v$, we calculate $N$, the sum of factorials of the elements of $v$. Then we convert $N$ back to a combination of digits $v'$. If $v = v'$, then $N$ is one of the numbers that we are looking for, so we add it to the total.